package structure.array;


import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import java.util.Stack;

/**
 * 地址：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
 * <p>
 * 题目：剑指 Offer 39. 数组中出现次数超过一半的数字
 * <p>
 * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 * <p>
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 * <p>
 * 示例1:
 * <p>
 * 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
 * 输出: 2
 */
public class Leetcode_Sword_Offer_39 {
    public static void main(String[] args) {

        int[] input = new int[]{1, 2, 3, 2, 2, 2, 5, 4, 2};

        System.out.println(majorityElement(input));


    }

    /**
     * 解法2：
     * 思路： 随机取数组里面的一个数，判断这个数的次数是否是众数
     * <p>
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * <p>
     * 执行结果：通过
     * 执行用时：15 ms, 在所有 Java 提交中击败了21.76%的用户
     * 内存消耗：43.3 MB, 在所有 Java 提交中击败了66.75%的用户
     * <p>
     * 可以优化的地方在哪里？
     * 优化空间，开辟了一个 Map 的空间
     *
     * @return
     */
    public static int majorityElement(int[] nums) {
        int majorityCount = nums.length / 2;
        while (true) {
            int curNum = nums[rangeIndex(0, nums.length)];
            if (curNumCount(nums, curNum) > majorityCount) {
                return curNum;
            }
        }
    }

    private static int curNumCount(int[] nums, int curNum) {
        int count = 0;
        for (int num : nums) {
            if (num == curNum) {
                count++;
            }
        }
        return count;
    }

    private static int rangeIndex(int start, int end) {
        return new Random().nextInt(end - start) + start;
    }


    /**
     * 解法1：
     * 思路： Map 来存储 key:数字，value 为次数
     * <p>
     * 时间复杂度：O(N)
     * 空间复杂度：O(N)
     * <p>
     * 执行结果：通过
     * 执行用时：15 ms, 在所有 Java 提交中击败了21.76%的用户
     * 内存消耗：43.3 MB, 在所有 Java 提交中击败了66.75%的用户
     * <p>
     * 可以优化的地方在哪里？
     * 优化空间，开辟了一个 Map 的空间
     *
     * @return
     */
    public static int majorityElement1(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            Integer count = map.getOrDefault(num, 0);
            if (count >= (nums.length / 2)) {
                return num;
            }
            map.put(num, count + 1);
        }
        return 0;
    }
}
